/*
 * @lc app=leetcode.cn id=915 lang=cpp
 *
 * [915] 分割数组
 *
 * https://leetcode.cn/problems/partition-array-into-disjoint-intervals/description/
 *
 * algorithms
 * Medium (47.28%)
 * Likes:    175
 * Dislikes: 0
 * Total Accepted:    30.8K
 * Total Submissions: 60.9K
 * Testcase Example:  '[5,0,3,8,6]'
 *
 * 给定一个数组 nums ，将其划分为两个连续子数组 left 和 right， 使得：
 *
 *
 * left 中的每个元素都小于或等于 right 中的每个元素。
 * left 和 right 都是非空的。
 * left 的长度要尽可能小。
 *
 *
 * 在完成这样的分组后返回 left 的 长度 。
 *
 * 用例可以保证存在这样的划分方法。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：nums = [5,0,3,8,6]
 * 输出：3
 * 解释：left = [5,0,3]，right = [8,6]
 *
 *
 * 示例 2：
 *
 *
 * 输入：nums = [1,1,1,0,6,12]
 * 输出：4
 * 解释：left = [1,1,1,0]，right = [6,12]
 *
 *
 *
 *
 * 提示：
 *
 *
 * 2 <= nums.length <= 10^5
 * 0 <= nums[i] <= 10^6
 * 可以保证至少有一种方法能够按题目所描述的那样对 nums 进行划分。
 *
 *
 */

// @lc code=start
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int partitionDisjoint(vector<int> &nums) {
        int n = nums.size();
        vector<int> left_max(n, INT_MIN), right_min(n, INT_MAX);
        left_max[0] = nums[0];
        right_min[n - 1] = nums[n - 1];
        for (int i = 1; i < n; ++i) {
            int j = n - 1 - i;
            left_max[i] = max(left_max[i - 1], nums[i]);
            right_min[j] = min(right_min[j + 1], nums[j]);
        }
        int index = 0;
        while (index < n - 1) {
            if (left_max[index] <= right_min[index + 1]) {
                break;
            }
            else {
                ++index;
            }
        }
        return index + 1;
    }
};
// @lc code=end
